#include <iostream>
#include <stack>
using namespace std;

template<class T>
class mstack
{
	template<class TT> //注意这边模板参数不一样
	friend ostream& operator<<(ostream& out, mstack<TT>& S);
public:
	mstack(){}
	~mstack(){}
	void push(const T& v);
	void pop();
	T& top(){return S.top();};
	T& max();
	bool empty(){return S.empty();}
private:
	stack<T> S;
	stack<T> maxS;
};

template<class TT>
ostream& operator<<(ostream& out, mstack<TT>& S)
{
	mstack<TT> temp;
	while(!S.empty())
	{
		temp.push(S.top());
		S.pop();
	}
	while(!temp.empty())
	{
		S.push(temp.top());
		out << temp.top() << " ";
		temp.pop();
	}
	return out;
}


template<class T>
void mstack<T>::push(const T& v)
{
	if(maxS.empty() || v > maxS.top())
		maxS.push(v);
	else
		maxS.push(maxS.top());
	S.push(v);
}

template<class T>
void mstack<T>::pop()
{
	S.pop();
	maxS.pop();	
}

template<class T>
T& mstack<T>::max()
{
	return maxS.top();	
}




int main()
{
	mstack<int> S;
	S.push(3);
	cout << S << " with max: " << S.max() << endl; 
	S.push(1);
	cout << S << " with max: " << S.max() << endl; 
	S.push(8);
	cout << S << " with max: " << S.max() << endl; 
	S.push(5);
	cout << S << " with max: " << S.max() << endl; 
	S.pop();
	cout << S << " with max: " << S.max() << endl; 
	S.pop();
	cout << S << " with max: " << S.max() << endl; 
	S.push(7);
	cout << S << " with max: " << S.max() << endl; 
	return 0;
}
